import java.util.PriorityQueue;
import java.util.Queue;

public class MergeKSortedLists {
    // 使用优先级队列的解法
    public ListNode mergeKLists1(ListNode[] lists) {
        // lambda 表达式(小根堆)
        Queue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);

        // 1.遍历这组链表的所有链表头节点
        for(ListNode x : lists) {
            if(x != null) {
                // 当前节点不为空, 才能入队列
                queue.offer(x);
            }
        }

        // 2.构建虚拟头节点
        ListNode virtualNode = new ListNode();
        ListNode last = virtualNode; // 尾指针, 用来进行尾插
        while(!queue.isEmpty()) {
            // 把当前节点进行尾插
            ListNode cur = queue.poll();
            last.next = cur;
            last = cur;

            // 当前节点指向所属链表的下一个节点(如果不为空的话)
            if(cur.next != null) {
                queue.offer(cur.next);
            }
        }

        return virtualNode.next;
    }

    // 递归法,先左再右, 然后合并这一左一右链表
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int left, int right) {
        // left==right,说明只有一个元素,返回当前元素即可
        if(left == right) {
            return lists[left];
        }
        // left都大于right了,说明没元素了, 返回null
        if(left > right) {
            return null;
        }

        // 1.中间点
        int mid = left + ((right - left) >> 1);
        // [left, mid]  [mid+1, right]
        ListNode cur1 = merge(lists, left, mid);
        ListNode cur2 = merge(lists, mid+1, right);

        // 2.合并两个链表
        ListNode virtualNode = new ListNode();
        ListNode last = virtualNode; // 尾指针
        while(cur1 != null && cur2 != null) {
            if(cur1.val < cur2.val) {
                last.next = cur1;
                last = cur1;
                cur1 = cur1.next;
            }else {
                last.next = cur2;
                last = cur2;
                cur2 = cur2.next;
            }
        }

        // 上面只能保证一个链表遍历完所有结点
        if(cur1 != null) {
            last.next = cur1;
            last = cur1;
        }
        if(cur2 != null) {
            last.next = cur2;
            last = cur2;
        }

        return virtualNode.next;
    }
}
